package com.atguigu.sort;

import java.util.Arrays;

/**
 * 插入排序
 *
 * 耗时:
 * work: 0.6s (实测很多次,都是这个结果,不知道为什么会这么快?)
 */
public class InsertSort {
    public static void main(String[] args) {
        int[] arr = ArrCreator.createRandArr(ArrCreator.testVelocitySize);
//        System.out.println(Arrays.toString(arr));
        ArrCreator.beforeSort();
        sort(arr);
        ArrCreator.afterSort();
//        System.out.println(Arrays.toString(arr));
    }

    /**
     * 插入法看起来好像优先级也不是很高, 但却是shell排序的前置算法.因而比较重要!!!
     *
     * 每一轮(i从0开始算)的特征:
     * 1. 最多进行i+2次赋值,最少进行0or1次赋值
     * 2. 可以保证前面i+2个结果是正确的
     * 3. 一共需要进行n-1轮
     *
     * @param arr
     */
    public static void sort(int[] arr){
        int insertVal;
        int insertIndex;

        for (int i = 1; i < arr.length; i++) {
            insertVal=arr[i];
            insertIndex=i-1;
            while(insertIndex>=0&&insertVal<arr[insertIndex]){
                arr[insertIndex+1]=arr[insertIndex];
                insertIndex--;
            }
            arr[insertIndex+1]=insertVal;
        }
    }
}
